package com.hspedu.newData.LCR;

import java.util.*;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-28 
 * @Version: 1.0
 */

public class LCR108单词接龙 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        return bfs(beginWord,endWord,wordList);
    }

    public int bfs(String beginWord,String endWord,List<String> wordList){

        Set<String> set = new HashSet<>(wordList);
        Set<String> visited = new HashSet<>();

        Queue<String> queue = new ArrayDeque<>();

        queue.add(beginWord);
        visited.add(beginWord);
        int len = 0;
        while (!queue.isEmpty()){
            len++;
            int len1 = queue.size();
            while (len1>0){
                String str = queue.poll();

                char[] charArray = str.toCharArray();

                for (int i = 0; i < charArray.length; i++) {

                    char old = charArray[i];
                    for (char j = 'a'; j <= 'z'; j++) {

                        charArray[i] = j;
                        String newStr = new String(charArray);
                        if (set.contains(newStr)&&!visited.contains(newStr)){
                            queue.add(newStr);
                            visited.add(newStr);

                            if (newStr.equals(endWord)){
                                return len+1;
                            }
                        }
                    }
                    charArray[i] = old;
                }
                len1--;
            }
        }

        return 0;
    }

}
